/* 1413. 逐步求和得到正数的最小值 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var minStartValue = function (nums) {
	for (let i = 1; ; i++) {
		let sum = i,
			flag = true
		for (const num of nums) {
			sum += num
			if (sum < 1) {
				flag = false
				break
			}
		}
		if (flag) {
			return i
		}
	}
}
/*
    贪心 要保证所有的累加和accSum 满足 sccSum + startValue >= 1
    只需要满足最小值 accSumMin 满足 accSumMin + stratValue >= 1

*/
var minStartValue = function (nums) {
	let accSum = 0,
		accSumMin = 0
	nums.forEach((num) => {
		accSum += num
		accSumMin = Math.min(accSumMin, accSum)
	})
	return -accSumMin + 1
}
/* 二分 */
var minStartValue = function (nums) {
	// total 为最小和，暂时不修改 _.min
	const total = nums.reduce((prev, next) => prev + next)
	if (total >= 0) return 1
	let left = 1,
		right = -total * nums.length + 1 // 保证右端点一定满足startValue的
	while (left < right) {
		const medium = Math.floor((left + right) / 2)
		if (valid(medium, nums)) {
			right = medium
		} else {
			left = medium + 1
		}
	}
	return left
}

const valid = (startValue, nums) => {
	for (const num of nums) {
		startValue += num
		if (startValue <= 0) {
			return false
		}
	}
	return true
}
const result = minStartValue([1, -2, -3])
console.log('minStartValue :>>', result)
